#pragma once
#include <iostream>
#include <cassert>

namespace mylist
{
    template <class T>
    struct ListNode
    {
        T _val = 0;
        ListNode *_next = nullptr;
        ListNode *_prev = nullptr;
        ListNode(const T &val = T()) : _val(val)
        {
        }
    };

    template <class T>
    class list;

    template <class T, class Ref, class Ptr>
    class ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListIterator<T, Ref, Ptr> self;

        Node *_node;

      
        friend class list<T>;

    public:
        ListIterator(Node *node = nullptr) : _node(node)
        {
        }

        Ref operator*()
        {
            return _node->_val;
        }
        Ptr operator->()
        {
            return &(_node->_val);
        }
        self &operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self operator++(int)
        {
            self &tmp = *this;
            _node = _node->_next;
            return tmp;
        }
        self operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self &operator--(int)
        {
            self &tmp = *this;
            _node = _node->_prev;
            return tmp;
        }

        bool operator==(const self &it) const
        {
            return it._node == _node;
        }

        bool operator!=(const self &it) const
        {
            return it._node != _node;
        }
    };

    template <class T>
    class list
    {

        typedef ListNode<T> Node;
        Node *_head = nullptr;
        size_t _size = 0;

    public:
        typedef ListIterator<T, T &, T *> iterator;
        typedef ListIterator<T, const T &, const T *> const_iterator;

        list()
        {
            Init();
        }

        list(size_t n, const T &val = T())
        {
            Init();
            while (n--)
            {
                push_back(val);
            }
        }
        list(iterator first, iterator last)
        {
            Init();
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }

        list(const list<T> &lt)
        {
            Init();
            const_iterator it = lt.cbegin();
            while (it != lt.cend())
            {
                push_back(*it);
                it++;
            }
        }

        void Init()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        iterator begin()
        {
            return _head->_next;
        }
        iterator end()
        {
            return _head;
        }

        const_iterator cbegin() const
        {
            return _head->_next;
        }
        const_iterator cend() const
        {
            return _head;
        }

        iterator insert(iterator pos, const T &val)
        {
            Node *newnode = new Node(val);
            Node *next = pos._node;
            Node *prev = next->_prev;

            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = next;
            next->_prev = newnode;

            _size++;
            return newnode;
        }

        iterator erase(iterator pos)
        {
            assert(!empty());
            Node *next = pos._node->_next;
            Node *prev = pos._node->_prev;

            prev->_next = next;
            next->_prev = prev;
            delete pos._node;
            _size--;
            return next;
        }
        void push_back(const T &val)
        {
            // Node *newnode = new Node(val);

            // if (newnode != nullptr)
            // {
            //     _head->_prev->_next = newnode;
            //     newnode->_prev = _head->_prev;

            //     _head->_prev = newnode;
            //     newnode->_next = _head;
            // }

            insert(end(), val);
        }

        void push_front(const T &val)
        {
            insert(begin(), val);
        }

        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }

        bool empty()
        {
            return _size == 0;
        }

        size_t size()
        {
            return _size;
        }
        void print()
        {
            for (auto &e : *this)
            {
                std::cout << e << " ";
            }
            std::cout << std::endl;
        }
    };

}